#include <stdio.h>
#include <stdlib.h>
#define InitSize 10 // 顺序表初始长度

// 静态顺序表
typedef struct
{
    int *data;   // 指向动态分配数组的指针
    int MaxSize; // 顺序表的最大容量
    int length;  // 顺序表的当前长度
} SeqList;

void InitList(SeqList &L);                  // 初始化
void ClearList(SeqList &L);                 // 销毁
bool ListEmpty(SeqList L);                  // 判空
int ListLength(SeqList L);                  // 长度
bool GetElem(SeqList L, int i, int &e);     // 按位查找
bool LocateElem(SeqList L, int w, int &e);  // 按值查找
bool ListInsert(SeqList &L, int i, int e);  // 插入
bool ListDelete(SeqList &L, int i, int &e); // 删除
void PrintList(SeqList L);                  // 输出

// 列表初始化
void InitList(SeqList &L)
{
    L.data = (int *)malloc(InitSize * sizeof(int));
    for (int i = 0; i < L.MaxSize; i++)
        L.data[i] = 0;
    L.length = 0;
    L.MaxSize = InitSize;
}

// 销毁
void ClearList(SeqList &L, int i, int &e)
{
    free(L.data);
    L.length = 0;
    L.MaxSize = 0;
    L.data = NULL;
}

// 判空
bool ListEmpty(SeqList L)
{
    return L.length == 0;
}

// 长度
int ListLength(SeqList L)
{
    return L.length;
}

// 按位查找
bool GetElem(SeqList L, int i, int &e)
{
    if (i >= L.length)
        return false;
    e = L.data[i];
    return true;
}

// 按值查找
bool LocateElem(SeqList L, int w, int &e)
{
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == w)
        {
            e = L.data[i];
            return true;
        }
    return false;
}

// 增加动态数组的长度
void IncreaseSize(SeqList &L, int len)
{
    int *p = L.data;
    L.data = (int *)malloc((L.MaxSize + len) * sizeof(int));
    for (int i = 0; i < L.length; i++)
        L.data[i] = p[i];
    L.MaxSize = L.MaxSize + len;
    free(p);
}

// 尾部插入
bool ListAppend(SeqList &L, int e)
{
    L.data[L.length] = e;
    L.length++;
    return true;
}

// 插入
bool ListInsert(SeqList &L, int i, int e)
{
    if (i < 0 || i > L.length)
        return false;
    if (L.length >= L.MaxSize)
        IncreaseSize(L, InitSize);
    if (L.length == i)
        return ListAppend(L, e);
    for (int j = L.length; j >= i; j--)
        L.data[j] = L.data[j - 1];
    L.data[i] = e;
    L.length++;
    return true;
}

// 删除
bool ListDelete(SeqList &L, int i, int &e)
{
    if (i < 0 || i >= L.length)
        return false;
    e = L.data[i];
    for (int j = i; j < L.length; j++)
        L.data[j] = L.data[j + 1];
    L.length--;
    return true;
}

// 输出
void PrintList(SeqList L)
{
    printf("顺序表: \t");
    printf("顺序表长度: %d\n", L.length);
    printf("数据: ");
    for (int i = 0; i < L.length; i++)
        printf("%d ", L.data[i]);
    printf("\n");
    
}

// int main()
// {
//     SeqList L;

//     // 初始化
//     InitList(L);
//     // 插入
//     ListInsert(L, 0, 1);
//     ListInsert(L, 0, 2);
//     ListInsert(L, 0, 5);
//     ListInsert(L, 2, 3);
//     PrintList(L);

//     // 判空
//     bool isEmpty = ListEmpty(L);
//     printf("\n线性表是否为空: %d\n", isEmpty);

//     // 长度
//     int length = ListLength(L);
//     printf("\n线性表长度: %d\n", length);

//     // 按位查找
//     int w;
//     GetElem(L, 2, w);
//     printf("\n查找到元素值为: %d\n", w);

//     // 按值查找
//     int i;
//     LocateElem(L, 2, i);
//     printf("\n查找到元素位置为: %d\n", i);

//     // 删除
//     int e;
//     ListDelete(L, 0, e);
//     printf("\n删除了: %d\n", e);
//     PrintList(L);

//     return 0;
// }